#include<stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

typedef int ElemType;

// 二叉排序树结点
typedef struct BSTNode{
    ElemType data;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

// 非递归查询
BSTNode *BST_Search(BSTree T, ElemType key){
    while (T!=NULL&&key!=T->data)
    {
        if(key < T->data) T=T->lchild;
        else T=T->rchild;
    }
    return T;
}

// 递归查询
BSTNode *BSTSearch(BSTree T, ElemType key){
    if (T==NULL) return NULL;
    if (key==T->data) return T;
    if (key < T->data){
        return BSTSearch(T->lchild, key);
    }else{
        return BSTSearch(T->rchild, key);
    }
}

// 递归插入
int BST_Insert(BSTree &T, int k){
    // 原树为空，新插入的结点为根结点
    if(T==NULL){
        T = (BSTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild=T->rchild=NULL;
        return 1;
    }
    else if(k<T->data) return BST_Insert(T->lchild, k);
    else BST_Insert(T->rchild, k);
}

// 非递归插入

// 构建二叉排序树
void Create_BST(BSTree &T, int str[], int n){
    T=NULL;
    int i=0;
    while (i<n)
    {
        BST_Insert(T, str[i]);
        i++;
    }
}

int main(){
    int str[8]={50,66,60,26,21,30,70,68}; 
    BSTree T;
    Create_BST(T, str, 8);
    printf("%d", BST_Search(T, 21)->data);
    system("pause");
    return 0;
}
